﻿//FUNKTIONIERT !

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Compiler
{
    //todo: SymbolComparer einbauen. Bei FollowSets auch
    public static class SetFactory
    {
        //FIRST-Mengen für alle Grammatik-Symbole. Daraus ergeben sich die First-Mengen beliebiger Wörter.
        public static FirstSets CreateFirstSets(Grammar grammar)
        {
            var EpsilonSet = new HashSet<Symbol>();
            EpsilonSet.Add(Symbol.Epsilon);

            var Terminals = grammar.getTerminals();
            var Productions = grammar.Productions;

            //Initialize
            var FirstSet = new Dictionary<Symbol, HashSet<Symbol>>();
            foreach (var terminal in Terminals)
            {
                //Rule 1: a € First(a)
                var set = new HashSet<Symbol>();
                set.Add(terminal);
                FirstSet.Add(terminal, set);
            }
            var eofset = new HashSet<Symbol>();
            eofset.Add(Symbol.EOF);
            FirstSet.Add(Symbol.EOF, eofset);


            foreach (var meta in Productions.Keys)
            {
                //Rule 2: eps € First(X) wenn X->eps
                var set = new HashSet<Symbol>();
                FirstSet.Add(meta, set);

                foreach (var production in Productions[meta])
                {
                    if (production.isEpsilonProduction())
                        set.Add(Symbol.Epsilon);
                }

                Debug.Assert(set.Contains(Symbol.Epsilon) == !EpsilonSet.Except(set).Any());
            }

            //Rule 3.
            bool smthChanged;
            do
            {
                smthChanged = false;

                foreach (var meta in Productions.Keys)
                {
                    foreach (var production in Productions[meta])
                    {
                        var set = FirstSet[meta];
                        int countStart = set.Count;

                        for (int i = 0; i < production.Tail.Count; ++i)
                        {
                            Symbol symbol = production.Tail[i];
                            if (symbol == Symbol.Epsilon)
                                continue;

                            set.UnionWith(FirstSet[symbol].Except(EpsilonSet));

                            if (!FirstSet[symbol].Contains(Symbol.Epsilon))
                                break;
                            else if (i == production.Tail.Count - 1)
                                set.UnionWith(EpsilonSet);
                        }

                        smthChanged |= (countStart != set.Count);
                    }
                }

            } while (smthChanged);

            return new FirstSets(grammar, FirstSet);
        }



        public static FollowSets CreateFollowSets(Grammar grammar)
        {
            return CreateFollowSets(grammar, CreateFirstSets(grammar));
        }


        public static FollowSets CreateFollowSets(Grammar grammar, FirstSets FirstSet)
        {
            var EpsilonSet = new HashSet<Symbol>();
            EpsilonSet.Add(Symbol.Epsilon);

            var FollowSet = new Dictionary<Nonterminal, HashSet<Symbol>>();
            var NonTerminals = grammar.getNonterminals();
            var Productions = grammar.Productions;

            foreach (var meta in NonTerminals)
                FollowSet.Add(meta, new HashSet<Symbol>());

            //Rule 1.
            FollowSet[grammar.Start].Add(Symbol.EOF);

            bool smthChanged;
            do
            {
                smthChanged = false;

                foreach (var meta in Productions.Keys)
                {
                    foreach (var production in Productions[meta])
                    {
                        for (int i = 0; i < production.Tail.Count; ++i)
                        {
                            var metaSymbol = production.Tail[i] as Nonterminal;

                            if (metaSymbol != null)
                            {
                                var set = FollowSet[metaSymbol];

                                int countStart = set.Count;

                                //Firstmenge für Zeichen NACH dem Metasymbol berechnen
                                var firstSetForRest = FirstSet.ForChain(production.Tail.Skip(i + 1).ToList());

                                //Rule 2
                                set.UnionWith(firstSetForRest.Except(EpsilonSet));

                                //Rule 3
                                if (i == production.Tail.Count - 1 || firstSetForRest.Contains(Symbol.Epsilon))
                                    set.UnionWith(FollowSet[meta]);

                                smthChanged |= (countStart != set.Count);
                            }
                        }
                    }
                }
            } while (smthChanged);

            return new FollowSets(FollowSet);
        }
    }
}
